The invention relates to a method of compressing digital image data, comprising successive data groups of bits, the contents of which are the values of pixels of an image, in which method a check is made in a selection step whether a first condition is satisfied which at least stipulates that the data group has the same contents as one or more data groups following thereon, whereafter, if the first condition is satisfied, said data groups are replaced, in a compression step, by a compression code representing these data groups, and otherwise, in a copying step only the first data group is replaced by a code consisting of the contents of the data group, whereafter the above steps are repeated for the next data groups, the method also comprising an identification step for adding an identification code for characterizing the nature of the code.
The invention also relates to a system in which the method is applied.
Digital image data can be obtained, among other ways, by scanning a document with photosensitive sensors, e.g., CCDs. A document can be divided up into pixels by column and line scanning and then be represented by values corresponding to said pixels.
These values can in turn be represented by data groups of one or more bits. Either a number of bits together may represent a grey value or each bit can separately represent a black/white value of a pixel (a bitmap). In the case of a color scanner, the grey value could relate to a scanned color. A data group having different bits can therefore either reproduce a grey value or color value of a pixel corresponding to the data group, or reproduce a black/white value for pixels corresponding to each bit, e.g., as in the case of a half-tone image.
Digital image data of this kind are obtained, among other ways, in systems equipped with scanners, e.g., facsimile systems and digital copying machines. In addition, however, such digital image data can also be generated by special computers, e.g., word processors or electronic character systems.
Depending on the situation, there will be a need to store or transmit such data. However, with a conventional resolution of 300 dots per inch and only black or white pixels, an A4 document already requires 1 Mbyte or, in the case of an AO document, 16 Mbyte memory space or data for transmission. In such cases it is advantageous to compress the data with one of the many known compression methods, e.g., "predictive" coding, Q-coding or "READ" coding (Relative Address Coding: G4-facsimile standard).
However, these prior art compression methods appear to lead to complex compression and decompression circuits. The object of the method and system according to the invention is to provide a compression method which gives a simpler architecture.
Closer analysis shows that, irrespective of the compression method, one aspect contributing to the complexity of a compression or decompression system is the possibility of local and global data expansion.
Local data expansion occurs if a compression system temporarily generates a higher number of bits per unit of time than the number of bits that can be processed per unit of time. This occurs if there is little correlation between the data groups for compression. One compression method then adds more redundant code than is saved to the number of compressed bits. In the case, for example, of run length coding according to Group 2 Fax format, a number of bits are required to indicate the run length and a number of bits to show the data group from which the run length is constructed. In the case of image lines with short run lengths local data expansion can then occur.
Local data expansion also results in a decompression system temporarily asking for code at a higher tempo in order to generate pixels at a constant speed of data groups. To prevent the processing system or memory coupled thereto having to operate at these higher speeds, the code must be buffered.
If local data expansion takes too long, then global data expansion may occur. In that case, the number of bits required to compress a line or even an entire image is greater than the number of original bits required for the purpose. A situation of this kind is undesirable, since the code buffers may then possibly be too small. In addition there is a risk that the compressed image will no longer fit in a memory.
A check must therefore be made whether data expansion occurs. If data expansion is signalled, or if no compression can be achieved in this way, compression of the incoming data groups must be abandoned. The incoming data groups must then be directly copied in the code series. This series must then be preceded by a code indicating the number of copied data groups.
A method and system of this kind is described, for example, in Applicant's Netherlands patent application number 9201415, corresponding to copending U.S. patent application Ser. No. 08/375,512. Copying the data groups ensures that data expansion remains limited because compression is carried out only if compression cannot cause data expansion.
Nevertheless, the possibility thereof must be taken into account: copying requires extra data in the form of the code representing the number of copied data groups in order to indicate that data groups are involved in what is copied.
The detection and processing thereof will, however, involve extra overheads in both the code and the compression and decompression system requirements.